# Brilliant.org Hunger Games Submission
# by James Williams (maneframe)
# ******************************************************************************

# When I first came across this competition, I was immediately hooked. 
# I excitedly went about analyzing the problem (as best as I could, with my 
# admittedly rudimentary understanding of game theory), and thinking up 
# a myriad of intricate and complex strategies that I could implement 
# to try to outsmart all of the other algorithms.

# But, in the midst of all this excitement, I was hit with a sudden realization:

# The real game wasn't going to be played by the algorithms... I was actually 
# playing the real game, the "metagame", right now! I was thinking about the 
# wrong problem all along!

# ******************************************************************************

# I was thinking about the competition only in terms of the $1,000 prize. 
# In order to try to win that, my primary available course of action would 
# essentially be to:

# 	Strategy A: (Compete)
#		Try to develop a complex algorithm that tries to behave as optimally as
#		possible in any given scenario, in order to (hopefully) gain more food 
#		than any other algorithm (or outlive them), and thus win the entire 
#		game.

# But I remembered the Finalist prize, the 'I survived' t-shirt, which is given 
# to those who make algorithms that survive through to the end of the game. I
# realized that this opens up the opportunity for another possibily beneficial
# strategy.

# 	Strategy B: (Cooperate)
#		Develop a sub-optimal algorithm (as far as the grand prize is concerned)
#		that primarily hunts, in order to maximize the chances that the tribe 
#		receives extra food at the end of each round (given that this is the 
#		only net positive source of food for the tribe). If enough of the tribe
#		behaves similarly, the entire tribe can survive through to the end 
#		of the game and together recieve the lesser prize.

# ******************************************************************************
# (SIDE NOTE)
# Just how much hunting would it take for tribe survival? For a quick estimate:

# 	- Let X be the average ratio of hunts vs. total actions.
#	- Assuming the random integer m is uniformly distributed, each player
#		should recieve an extra 2X(P-1) units of food per round on average.
#	- Assuming a uniform distribution of hunting vs. slacking partners for each
#		player (i.e. no one is singled out), even a perfectly altruistic player
#		should lose 3(1-X)(P-1) food per round on average.

#	- So the breakeven point will be when 2X - 3(1-X) = 0, or X = 0.6
#		(i.e. 60% average hunting). The chance that the tribe might cooperate 
#		at this level seems low, but not altogether implausible, at least in my
#		opinion.

# ******************************************************************************

# So, I had a decision to make. Should I choose to compete, or should I try to 
# cooperate? However, by this point, the choice was already clear to me: I 
# wanted to pursue Strategy B.

# Why? Well, to put it simply, I don't really know. 

# Maybe it's because I don't feel very confident in my ability to develop a
# winning algorithm. Maybe it's because Strategy B seems simpler to write an 
# algorithm for, and I'm a little bit lazy. Maybe part of me hopes that my
# approach might stand out from among the crowd and catch someone's eye.

# Or, in the end, maybe it's because I'm human, and like many people, I often
# like to cooperate even when it's not necessarily the most "rational" choice, 
# as far as pure self-gain is concerned.

# And in the end, does it really matter? In my opinion, this competition is
# ultimately about two things: fun and learning.

# And as far as those are concerned, I think I've already succeeded.

# ******************************************************************************

# So, given that my goal is the long-term survivability of the tribe, exactly 
# what sort of algorithm should I develop?

# Now, a perfectly altruistic algorithm, one that hunts every time, will clearly
# maximize the chances that the tribe receives extra food for any one particular
# round. However, I don't think this is the best strategy to promote survival
# for the tribe in the long run. 

# Rather, it seems that there is a beneficial role for reciprocity, just as we
# can observe in natural cooperative systems. I would argue that the best 
# algorithm should try to hunt with those who also hunt with us, and slack with 
# those who slack with us, thus hopefully discouraging them from future
# slacking, lest they risk ultimately hastening their own starvation.

# This is the underlying strategy behind the famously successful 'Tit-for-Tat'
# algorithm for the standard iterative Prisoner's Dilemma. At its core, the 
# strategy is simply to base your choice each round on whatever your opponent
# chose last. In essence, my algorithm is simply an extension of this strategy
# applied collectively.

# ******************************************************************************

# Algorithm Overview:

#	Each round, choose a number of players with the lowest reputations,
#	according to the percentage of slacking that occurred among the rest of the 
#	tribe during the previous round, and slack with them while hunting with all
#	of the rest.

#	(e.g. if the other players slacked 10% of the time last round, choose the 
#	bottom 10% of the tribe, according to reputation)

slacking_ratio = 0.0 # Always hunt for the first round

# Store in order to calculate the ratio in round_end
other_player_count = 0 
num_slacked_with = 0 

def hunt_choices(round_number, current_food, current_reputation, m, 
            player_reputations):
	global other_player_count, slacking_ratio, num_slacked_with

	other_player_count = len(player_reputations)

	# Begin by planning to hunt with everyone
	hunt_decisions = ['h' for x in player_reputations]

	# Decide how many players to slack with
	num_slacked_with = int(slacking_ratio * other_player_count)	
	
	# Get a list of tuples for each reputation: (original_index, reputation) 
	# and sort them by ascending order
	reputation_tuples = list(enumerate(player_reputations))
	reputation_tuples = sorted(reputation_tuples, key=lambda x: x[1])

	# Loop through the first tuples (i.e. the lowest reputation players)
	# and change the decision array to slack with them
	for tuple_index in range(num_slacked_with):
		original_index = reputation_tuples[tuple_index][0]
		hunt_decisions[original_index] = 's'

	return hunt_decisions

def hunt_outcomes(food_earnings):
	pass

def round_end(award, m, number_hunters):
	global other_player_count, slacking_ratio, num_slacked_with

	# Calculate the percentage of slacking decisions made by other players
	if other_player_count >= 1:
		# There are (P-1) other players, and each made (P-1) decisions
		other_decisions = other_player_count ** 2
		
		# The number of times we personally decided to hunt last round
		num_hunted_with = other_player_count - num_slacked_with
		
		# The total number of other decisions to hunt/slack
		other_hunt_decisions = (number_hunters - num_hunted_with)
		other_slack_decisions = other_decisions - other_hunt_decisions
				
		slacking_ratio = float(other_slack_decisions) / other_decisions